﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Windows.Controls;
using System.Windows;
using System.Windows.Media;

namespace Algoritmos_de_Ordenação.Algoritmos
{
    public class HeapSort : DrawingRegion
    {
        public HeapSort()
        {

        }
        
        public HeapSort(TabItem tabItem)
            : base(tabItem, TabType.Heap)
        {

        }

        int comparisons = 0;
        int swaps = 0;
        
        
        protected override void DoSort()
        {
            comparisons = 0;
            swaps = 0;
                        
            sorted = false;
                        
            heapSort();
            
            endSorting(comparisons, swaps);

        }

        int[] vetor;
        void heapSort()
        {
            vetor = new int[numElemArray + 1];
            vetor[0] = numberArray[0];
            for (int i = 1; i < numElemArray + 1; i++)
            {
                vetor[i] = numberArray[i - 1];
            }
            
            buildMaxHeap();//4
            for (int i = numElemArray; i >= 2; i--)//6
            {
                compareTwoThread(0, i - 1);
                wf();                    
                swapTwoThread(0, i - 1);
                swaps++;
                updateInformationsThread(SortStatus.Sorting, comparisons, swaps);
                updateGBThread(7);
                int temp = vetor[1];
                vetor[1] = vetor[i];
                vetor[i] = temp;

                numberArray[0] = numberArray[i - 1];//8
                numberArray[i - 1] = temp;

                tamHeap--;

                maxHeapify(1);//11
                }
        }

        int tamHeap;
        void buildMaxHeap()
        {
            tamHeap = numElemArray;
            for (int i = (int)Math.Floor(numElemArray / 2.0); i >= 1; i--)//19
            {
                updateGBThread(20);
                maxHeapify(i);//21
            }
        }

        void maxHeapify(int i)
        {
            int left = 2 * i;
            int right = 2 * i + 1;
            int maior = i;
            
            if (left <= tamHeap)//31
            {
                wf();
                updateGBThread(30);
                compareTwoThread(i - 1, left - 1);
                comparisons++;
                if (vetor[left] > vetor[i])
                {
                    maior = left;
                }
                else maior = i;
                updateInformationsThread(SortStatus.Sorting, comparisons, swaps);
            }

            if (right <= tamHeap)//35
            {
                wf();
                compareTwoThread(maior - 1, right - 1);
                updateGBThread(34);
                comparisons++;
                if (vetor[right] > vetor[maior])
                {
                    maior = right;
                }
                updateInformationsThread(SortStatus.Sorting, comparisons, swaps);
            }
            
            wf();
            compareTwoThread(maior - 1, i - 1);
            comparisons++;
            updateInformationsThread(SortStatus.Sorting, comparisons, swaps);
            updateGBThread(37);
            if (maior != i)//38
            {
                wf();
                swapTwoThread(maior - 1, i - 1);
                updateGBThread(39);
                int temp = vetor[i];
                vetor[i] = vetor[maior];
                vetor[maior] = temp;

                numberArray[i - 1] = numberArray[maior - 1];//40
                numberArray[maior - 1] = temp;
                swaps++;
                updateInformationsThread(SortStatus.Sorting, comparisons, swaps);
                maxHeapify(maior);//42
            }

        }
    }
}
